# -*- coding: utf-8 -*-
"""
structure analysis based on lyric only by finding repetition

the basic problem : what is the structure of a lyric, from a larger scale view
or smaller view the result may be different
"""

from Lyric import Lyric
from common_func import _sen_similar,print_seg,_insertlist,similarthres
from suffix_tree_substring import get_frequent_common,get_common_length
import re,copy
import simplejson

import logging
logging.basicConfig(format='%(levelname)s:%(message)s', level=logging.DEBUG)

sadebug = False
#sadebug = True

def analysis(lyric):
    linelist = lyric.getlinelist()
    return _ana1(linelist)

def _ana1(linelist):
    """
    use the suffix array for the longest repeated substring finding
    """
    # TODO this function is too long

    bitnum = 2

    # create the suffix structure for comparison
    name_list = range(len(linelist))
    for i in range(1,len(linelist)):
        for j in range(i):
            if linelist[i]['content'] == linelist[j]['content']:
                name_list[i] = name_list[j]
                break

    # TODO change name? 
    # index_name_list seem to be used for the sub string record
    name_str = ""
    index_name_list = []
    for i,n in enumerate(name_list):
        name_str += "%02d"%(n) # TODO change with bitnum here
        index_name_list.append( (i,n) )
        if sadebug:
            logging.debug("%d, %s"%(n,linelist[i]['content'].decode('utf-8')))
    index_name_list_list = [ index_name_list ]

    seg_list = []
    iter_num = 0
    while True:
        iter_num += 1
        if sadebug:
            logging.debug("### begin of iter %d ###"%(iter_num))
            logging.debug('index name list list')
            for index_name_list in index_name_list_list:
                begin_index = index_name_list[0][0]
                end_index = index_name_list[-1][0] + 1  #end_index is the number after
                logging.debug( name_str[begin_index*bitnum:end_index*bitnum] )
        
        # build the suffix array for each of the index_name_list
        suffix_array = []
        for index_name_list in index_name_list_list:
            begin_index = index_name_list[0][0]
            end_index = index_name_list[-1][0]+1  #end_index is the number after

            # for each substring structure, create the suffix array for it
            for i in range(begin_index,end_index):
                suffix_array.append(
                        (i, end_index, name_str[i*bitnum:end_index*bitnum]) )
        suffix_array.sort( lambda x,y:cmp(x[2],y[2]) )

        # after get the longest common string, 
        # rebuild the index_name_list_list, store the new structure
        # TODO trying, use the length*freq as the criter
        max_len = -1
        sub_str = ""
        for i in range( len(suffix_array)-1 ):
            # compare with i+1
            start1 = suffix_array[i][0]
            start2 = suffix_array[i+1][0]
            com_len = get_common_length( 
                    suffix_array[i][2], suffix_array[i+1][2] ,
                    start1*2 , start2*2)

            tmp_str = suffix_array[i][2][:com_len]
            count = 0
            for index_name_list in index_name_list_list:
                begin_index = index_name_list[0][0]
                end_index = index_name_list[-1][0]+1  #end_index is the number after
                sub_seg_str = name_str[begin_index*bitnum:end_index*bitnum]
                count += sub_seg_str.count(tmp_str)
            weight = com_len * count
            # TODO change this weight
            #print 'aaa',suffix_array[i],suffix_array[i+1],
            #print tmp_str,com_len,count

            # TODO this is the debug part
            if weight > max_len:
                max_len = weight
                sub_str = suffix_array[i][2][:com_len]
                if sadebug:
                    logging.debug("%d,%s,%s,%s,%d,%d"%
                        (max_len,sub_str,suffix_array[i][2],suffix_array[i+1][2],start1*2,start2*2))

        if sadebug:
            logging.debug( 'best sub str : %s'%sub_str )

        # get the real sub , not found the best match, then break
        if len(sub_str) < 3*bitnum:
            break

        # find all suffix_array in current index_name_list_list for re-build
        # store the new structure
        new_index_name_list = []
        for index_name_list in index_name_list_list:
            begin_index = index_name_list[0][0]
            end_index = index_name_list[-1][0]+1
            tmp_name_str = name_str[begin_index*bitnum:end_index*bitnum]

            #print tmp_name_str,sub_str
            if tmp_name_str.count(sub_str) == 0:
                new_index_name_list.append( copy.deepcopy(index_name_list) )
                continue
            else:
                m_list = []
                for m in re.finditer( sub_str,tmp_name_str ):
                    m_list.append(m)
                
                # check divide with bitnum
                for m in m_list:
                    if m.start() % bitnum != 0 or m.end() % bitnum != 0:
                        raise Exception(
                        ' should be multiplier of 2 %d,%d'%(m.start(),m.end()))

                if len(m_list) == 1:
                    #print 'only one match'
                    m = m_list[0]   # check here
                    start_index = m.start() / bitnum 
                    end_index = m.end() / bitnum - 1
                    
                    # seg list is the start and end index( not endindex+1 )
                    seg_list.append(
                        (index_name_list[m.start()/bitnum][0],
                            index_name_list[m.end()/bitnum - 1][0]) ) 
                     
                    # update the index_name_list
                    if sub_str == tmp_name_str:
                        continue
                    elif m.start() == 0:
                        new_index_name_list.append(
                                index_name_list[m.end()/bitnum:] )
                    elif m.end() == len(tmp_name_str):
                        new_index_name_list.append(
                                index_name_list[:m.start()/bitnum] )
                    else:
                        new_index_name_list.append(
                                index_name_list[:m.start()/bitnum] )
                        new_index_name_list.append( 
                                index_name_list[m.end()/bitnum:] )
                else:
                    #print 'match info'
                    #for m in m_list:
                    #    print m.start(),m.end()

                    # multiple match
                    # 1 process the space ahead of the first match
                    if m_list[0].start() != 0:
                        new_index_name_list.append(
                                index_name_list[:m_list[0].start()/bitnum])

                    # 2 each match and the space behind the match
                    for i in range(len(m_list)-1):

                        seg_list.append(
                        (index_name_list[m_list[i].start()/bitnum][0],
                            index_name_list[m_list[i].end()/bitnum - 1][0]) )

                        if m_list[i].end() != m_list[i+1].start():

                            new_index_name_list.append(
                                index_name_list[
                                    m_list[i].end()/bitnum:
                                    m_list[i+1].start()/bitnum])

                    # 3 the last match and the space to the end
                    seg_list.append(
                        (index_name_list[m_list[-1].start()/bitnum][0],
                            index_name_list[m_list[-1].end()/bitnum - 1][0]) )
                    if m_list[-1].end() != len(tmp_name_str):
                        new_index_name_list.append(
                                index_name_list[m_list[-1].end()/bitnum:])

        # re-assign the index_name_list_list
        index_name_list_list = new_index_name_list
        """
        print 'new sub sequence'
        for index_name_list in index_name_list_list:
            print index_name_list[0][0],index_name_list[-1][0]
        print 'seg'
        for seg in seg_list:
            print seg[0],seg[1]
        """
    # end of the while iteration

    seg_list.sort(lambda x,y:cmp(x[0],y[0]))
    new_seg_list = []

    #print 'org seg list',seg_list
    if seg_list[0][0] != 0:
        new_seg_list.append( (0,seg_list[0][0]-1))
    for i in range(len(seg_list)-1):
        new_seg_list.append(seg_list[i])
        if seg_list[i][1] + 1 != seg_list[i+1][0]:
            new_seg_list.append( (seg_list[i][1]+1,seg_list[i+1][0]-1) )
    new_seg_list.append(seg_list[-1])
    #print new_seg_list
    # TODO process the last one
    if seg_list[-1][1]+1 < len(linelist):
        new_seg_list.append( (seg_list[-1][1]+1,len(linelist)-1) )
    """
    print new_seg_list
    for i,seg in enumerate(new_seg_list):
        print 'seg',i,seg[0],seg[1]
        for j in range(seg[0],seg[1]+1):
            print linelist[j]['content'].decode('utf-8')
        #return 
    """
    return new_seg_list

if __name__ == "__main__":
    #c = get_common_length("1819200910111200010203181920091011120910111209101112","181920091011120910111209101112",36,58)
    #a = "1819200910111200010203181920091011120910111209101112"
    #print c,a[:c]
    #print get_frequent_common(["0001020304050607080910111213141516171819200910111200010203181920091011120910111209101112"],2)
    #exit()
    
    l = Lyric()
    #fname = "harrybobo.lrc"
    #fname = "wangfei.txt"
    #fname = "she-toodetail.lrc"
    #fname = "zhongguoweidao.lrc"
    fname = "yinnierzai.lrc"
    l.loadfile(fname)
    linelist = l.getlinelist()


    segs = analysis(l)
    print segs

    for seg in segs:
        print seg
        for i,line in enumerate(linelist):
            if i >= seg[0] and i <= seg[1]:
                print i,str(line['time'])+":"+line['content'].decode('utf-8')

